iT邦幫忙

2024 iThome 鐵人賽

DAY 16
0

題目

539. Minimum Time Difference
難度: 中等偏易

題意

給定一字串陣列timePoints,每個字串為HH:MM格式的24小時制時間。
求任兩對時間差之最小值(時間差可以跨過午夜,以分鐘數回傳)

思路

題目要求回傳值以分鐘計算,因此先將字串轉換成整數,HH * 60 + MM

將分鐘時間點排序好,兩兩相鄰的時間差取最小的。
排序過的時間點,相鄰為1的差距必不大於相鄰為2的差距,因此排序好只需搜尋兩兩相鄰的差即可。
要注意尾到頭(跨夜)的差也要列入計算。

實作

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes;
        for(auto str : timePoints)
        {
            int curr = ((str[0] - '0') * 10 + (str[1] - '0')) * 60 + ((str[3] - '0') * 10 + (str[4] - '0'));
            minutes.push_back(curr);
        }
        sort(minutes.begin(), minutes.end());
        
        int n = minutes.size();
        int res = 24 * 60 - (minutes.back() - minutes.front());
        for(int i = 1; i < n; i++)
            res = min(res, minutes[i] - minutes[i - 1]);
    return res;
    }
};

分析

若時間點的數量為N
時間複雜度: O(NlogN),排序
空間複雜度: O(N),儲存時間點

結果

Time Submitted Status Runtime Memory Language
09/16/2024 11:14 Accepted 15 ms 17.5 MB cpp

小記

連續兩天用手機刷題,眼睛快瞎了
手機版鐵人發文還有bug,會自己跳轉畫面,最後切電腦版網頁才成功發文


上一篇
[9/15] 最長子陣列中母音偶數個
下一篇
[9/17] 中秋節快樂
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言